// @coding: utf-8

/*
给定单链表head节点，判定是否是回文链表
*/

#include <iostream>
#include <vector>


class SLinkedNode
{
public:
    int value = 0;
    SLinkedNode* next;
};

void add_to_tail(SLinkedNode* head, SLinkedNode* node)
{
    auto tail = head;
    while (tail->next)
        tail = tail->next;
    tail->next = node;
}

void add_to_tail(SLinkedNode* head, int value)
{
    auto node = new SLinkedNode;
    node->value = value;
    add_to_tail(head, node);
}

SLinkedNode* vector_to_slinked_list(const std::vector<int>& vec)
{
    if (vec.empty())
        return nullptr;
    auto head = new SLinkedNode;
    SLinkedNode* prev = nullptr;
    for (std::size_t idx = 0; idx < vec.size(); ++idx)
    {
        if (!prev)
        {
            prev = head;
            prev->value = vec[idx];
            continue;
        }
        auto node = new SLinkedNode;
        node->value = vec[idx];
        prev->next = node;
        prev = node;
    }
    return head;
}

SLinkedNode* reversal(SLinkedNode* head)
{
    if (!head)
        return nullptr;
    SLinkedNode* prev = nullptr;
    SLinkedNode* cur = head;
    SLinkedNode* next = head->next;
    while (cur)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = next ? next->next : nullptr;
    }
    return prev;
}

bool is_palindrome(SLinkedNode* head)
{
    // 空或者只有一个节点
    if (!head || !head->next)
        return true;
    SLinkedNode* slow_node = head;
    SLinkedNode* fast_node = head;
    SLinkedNode* mid_node = nullptr;
    // 找到中间位置
    while (fast_node->next && fast_node->next->next)
    {
        fast_node = fast_node->next->next;
        slow_node = slow_node->next;
    }
    mid_node = slow_node;
    // 分割为 [head,mid] [mid,tail]
    SLinkedNode* left_head = head;
    SLinkedNode* right_head = reversal(mid_node->next);
    SLinkedNode* left_cur = left_head;
    SLinkedNode* right_cur = right_head;
    while (right_cur)
    {
        if (left_cur->value != right_cur->value)
            return false;
        left_cur = left_cur->next;
        right_cur = right_cur->next;
    }
    return true;
}

int main()
{
    std::vector<int> data{1,2,2,1};
    auto head = vector_to_slinked_list(data);
    head = reversal(head);
    head = reversal(head);
    bool result = is_palindrome(head);
    return 0;
}